//给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。 
//
// 说明：不要使用任何内置的库函数，如 sqrt。 
//
// 示例 1： 
//
// 输入：16
//输出：True 
//
// 示例 2： 
//
// 输入：14
//输出：False
// 
// Related Topics 数学 二分查找 
// 👍 168 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：有效的完全平方数
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P367_ValidPerfectSquare {
    public static void main(String[] args) {
        Solution solution = new P367_ValidPerfectSquare().new Solution();
        MyUtil.print(solution.isPerfectSquare(16));
        MyUtil.print(solution.isPerfectSquare(14));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isPerfectSquare(int num) {
            if (num <= 1) {
                return true;
            }
            long left = 1, right = num / 2;
            while (left <= right) {
                long mid = (right - left) / 2 + left;
                if (num > mid * mid) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return left * left == num || right * right == num;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}